package com.ctl.algorithm;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
/*3.1 前序遍历二叉树

        给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
        3
        / \
        9 20
        / \
        15 7
        输出 3,9,20,15,7*/
public class BinaryTreeLeftRightPrintByLevel {
    static class Node {
        public Node(int num) {
            this.num = num;
        }
        public int num;
        public Node left;
        public Node right;

        @Override
        public String toString() {
            return "Node{" +
                    "num=" + num +
                    '}';
        }
    }

    static AtomicInteger indexA = new AtomicInteger();
    static List<Map<Integer, List<Integer>>> list = new ArrayList<>();

    public static void main(String[] args) {
        Node root = getNodeTree();
        int level = 1;
        indexA.set(1);
        printNode(root, indexA, level);
        System.out.println("-------------------------------");
        list.stream().forEach(map-> System.out.println(map));
    }

    private static Node getNodeTree() {
        //level1
        Node root = new Node(1);
        //level2
        Node left2 = new Node(2);
        Node right2 = new Node(3);
        root.left = left2;
        root.right = right2;
        //level3
        Node left2_left3 = new Node(4);
        Node left2_right3 = new Node(5);
        left2.left = left2_left3;
        left2.right = left2_right3;
        Node right2_left3 = new Node(6);
        Node right2_right3 = new Node(7);
        right2.left = right2_left3;
        right2.right = right2_right3;
        //leve4
        Node left2_left3_left4 = new Node(8);
        Node left2_left3_right4 = new Node(9);
        left2_left3.left = left2_left3_left4;
        left2_left3.right = left2_left3_right4;

        Node left2_right3_left4 = new Node(10);
        Node left2_right3_right4 = new Node(11);
        left2_right3.left = left2_right3_left4;
        left2_right3.right = left2_right3_right4;

        Node right2_left3_left4 = new Node(12);
        Node right2_left3_right4 = new Node(13);
        right2_left3.left = right2_left3_left4;
        right2_left3.right = right2_left3_right4;

        Node right2_right3_left4 = new Node(14);
        Node right2_right3_right4 = new Node(15);
        right2_right3.left = right2_right3_left4;
        right2_right3.right = right2_right3_right4;
        return root;
    }


    /**
     * @param node current node
     * @param indexA this merthod run times
     * @param level node lever
     */
    public static void printNode(Node node, AtomicInteger indexA, int level) {
        if (node != null) {
            if (list.size() < level) {
                Map<Integer, List<Integer>> map = new HashMap<>();
                map.put(level, new ArrayList<>());
                list.add(map);
            }
            list.get(level - 1).get(level).add(node.num);
            System.out.println(node.num + "\t\t\t" + indexA.get() + "\t\t\t" + level+"\t\t\t"+node);
            indexA.incrementAndGet();

        }
        level++;
        if (node.left != null) {
            printNode(node.left, indexA, level);
        }
        if (node.right != null) {
            printNode(node.right, indexA, level);
        }
    }
}
//1			1			1
//2			2			2
//4			3			3
//8			4			4
//9			5			4
//5			6			3
//10			7			4
//11			8			4
//3			9			2
//6			10			3
//12			11			4
//13			12			4
//7			13			3
//14			14			4
//15			15			4
//-------------------------------
//{1=[1]}
//{2=[2, 3]}
//{3=[4, 5, 6, 7]}
//{4=[8, 9, 10, 11, 12, 13, 14, 15]}
